W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Na każdym polu kartki w kratkę, składającej się z kwadratów jednostkowych, zapisano jedną liczbę całkowitą. W tym zadaniu interesują nas prostokąty arytmetyczne położone na tej kartce, czyli takie prostokąty złożone z kwadratów jednostkowych, że liczby w każdym wierszu i w każdej kolumnie tworzą ciągi arytmetyczne. Przypomnijmy, że ciąg arytmetyczny to ciąg liczbowy, w którym każde dwa kolejne wyrazy różnią się o tę samą liczbę.
Na danej kartce w kratkę poszukujemy największego prostokąta arytmetycznego, tj. obejmującego najwięcej kwadratów jednostkowych. Przykładowo, największy prostokąt arytmetyczny na poniższej kartce składa się z dziewięciu kwadratów jednostkowych:
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów testowych opisanych w dalszej części wejścia. Opis każdego zestawu rozpoczyna się od wiersza z dwiema liczbami całkowitymi i (). W każdym z kolejnych wierszy znajduje się liczb całkowitych z zakresu od do . Są to liczby wpisane w poszczególne kwadraty jednostkowe kartki w kratkę. Rozmiar każdego pliku wejściowego będzie nie większy niż 20 MB.
Należy wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych. Odpowiedzią dla jednego zestawu jest jedna liczba całkowita równa liczbie kwadratów jednostkowych zawartych w największym prostokącie arytmetycznym na kartce opisanej w danym zestawie.
Dla danych wejściowych:
2 4 4 5 3 5 7 2 4 4 4 3 5 3 1 6 3 2 4 2 3 0 1 2 1 2 3
poprawną odpowiedzią jest:
9 6
Autor zadania: Jakub Radoszewski.